Poor pigs

Time: O(1); Space: O(1); easy

There are 1000 buckets, one and only one of them contains poison, the rest are filled with water. They all look the same. If a pig drinks that poison it will die within 15 minutes. What is the minimum amount of pigs you need to figure out which bucket contains the poison within one hour.

Answer this question, and write an algorithm for the follow-up general case.

Example 1:

Input: buckets = 1000, minutesToDie = 15, minutesToTest = 60

Output: 5

General case:

If there are n buckets and a pig drinking poison will die within m minutes, how many pigs (x) you need to figure out the poisonous bucket within p minutes? There is exactly one bucket with poison.

Notes:

  • A pig can be allowed to drink simultaneously on as many buckets as one would like, and the feeding takes no time.

  • After a pig has instantly finished drinking buckets, there has to be a cool down time of m minutes. During this time, only observation is allowed and no feedings at all.

  • Any given bucket can be sampled an infinite number of times (by an unlimited number of pigs).

Hints:

  1. What if you only have one shot? Eg. 4 buckets, 15 mins to die, and 15 mins to test.

  2. How many states can we generate with x pigs and T tests?

  3. Find minimum x such that (T+1)^x >= N

[1]:

import math

class Solution1(object):
    def poorPigs(self, buckets, minutesToDie, minutesToTest) -> int:
        """
        :type buckets: int
        :type minutesToDie: int
        :type minutesToTest: int
        :rtype: int
        """
        return int(math.ceil(math.log(buckets) / math.log(minutesToTest / minutesToDie + 1)))

[3]:

s = Solution1()
buckets, minutesToDie, minutesToTest = 1000, 15, 60
assert s.poorPigs(buckets, minutesToDie, minutesToTest) == 5